package quicksorttester;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * @author Zbyszko
 */
public class QuickSort {
    
    
    private Integer[] numbers;
    //private List<Integer> numbers;
    private int m,temp;//, pivot;
    private int middle;
    private int i;
    private List<Integer> numb;
    private int comparisonCounter;
    
    private List<Integer> getList(Integer[] tmp){
        List<Integer> res = new ArrayList<Integer>();        
        for(int a = 0; a < tmp.length; a++){
            res.add(tmp[a]);
        }        
        return res;
    }
    
    public int enableQuickSort(Integer[] numbers){
        comparisonCounter = -1;
        if(numbers != null || numbers.length != 0) {            
            List<Integer> tmpList = getList(numbers);
            //System.out.println(tmpList.toString());
            comparisonCounter = 0;
            //performSorting(tmpList);
            this.numbers = numbers;
            performSorting(0, numbers.length-1);
            //System.out.println(Arrays.toString(this.numbers));
        }  
        else {
            System.err.println("Unable to perform sorting...");
        }
        return comparisonCounter;
    }
    
    private List<Integer> concatenate(List<Integer> left, int p, List<Integer> right){
        numb = new ArrayList<Integer>();
        for(int j = 0; j < left.size(); j++){
            numb.add(left.get(j));
        }
        numb.add(p);
        for(int j = 0; j < right.size(); j++){
            numb.add(right.get(j));
        }
        
        //System.out.println("concatenate check: "+numb.toString());
        return numb;
    }
    
    private List<Integer> performSorting(List<Integer> array){
        //System.out.println("ps check: "+array.toString());
        if(array.size() > 1){
            i = 0;
            //middle = (array.size()-1)/2;
            //int pivot = array.remove(middle);
            int pivot = array.remove((array.size()-1)/2);
            
            List<Integer> less = new ArrayList<Integer>();
            List<Integer> greater = new ArrayList<Integer>();
            while(i < array.size()){
                //if(i != middle){
                    if(array.get(i) <= pivot){
                        less.add(array.get(i));                
                    } else {
                        greater.add(array.get(i));
                    }
                //}
                comparisonCounter++;
                i++;
            }
            return concatenate(
                    performSorting(less), 
                    pivot, 
                    performSorting(greater)
                    );
        } else {
            return array;
        }
    }
        
    private boolean check(int x, int y){
        comparisonCounter++;
        if(x<y) return true;
        return false;
    }
    
    private void performSorting(int low, int  high){
        int pivotIndex = low + (high-low)/2;
        int pivot = numbers[pivotIndex];        
        i = low;
        m = high-1;               
        temp = numbers[pivotIndex];
        numbers[pivotIndex]=numbers[high];
        numbers[high]=temp;
        while(i <= m) {            
            if(numbers[i] <= pivot) {
                i++;
            } else {
                temp = numbers[i];
                numbers[i]=numbers[m];
                numbers[m]=temp;
                m--;
            }
            comparisonCounter++;
        }  
        temp = numbers[i];
        numbers[i]=numbers[high];
        numbers[high]=temp;
        if(low < i-1) {
            performSorting(low,i-1);
        }
        if(i+1 < high) {
            performSorting(i+1,high);
        }
    }
      
//    public String arrayToString(){
//        return Arrays.toString(numbers);
//    }
}
